﻿#ifndef __DONGNAOEDU_SORT_HPP__
#define __DONGNAOEDU_SORT_HPP__

#include <stddef.h> // for size_t
#include <stdlib.h> // for malloc/free
#include <string.h> // for memcpy
#include <algorithm>  // for std::min
#include <utility>    // for std::swap

// 函数声明
// void bubble_sort(T a[], size_t size) 冒泡函数
// void bubble_sort_optimized(T a[], size_t size) 冒泡函数优化版
// void select_sort(T a[], size_t size) 选择排序
// void insert_sort(T a[], size_t size) 插入排序
// void insert_sort_binary(T a[], size_t size) 插入排序二分版
// void shell_sort(T a[], size_t size)  希尔排序
// void merge_sort(T a[], size_t size) 归并排序
// void quick_sort(T a[], size_t size) 快速排序
// void heap_sort(T a[], size_t size) 堆排序
// void count_sort(T a[], size_t size) 基数排序

/*
 * 排序算法性能对比（元素数量：100000，最大值：99）
----------------------------------------------
冒泡排序 用时：18984 ms
冒泡排序（优化） 用时：19982 ms
选择排序 用时：5386 ms
插入排序 用时：3588 ms
插入排序（二分） 用时：3275 ms
希尔排序 用时：12 ms
归并排序 用时：9 ms
快速排序 用时：6 ms
堆排序 用时：17 ms
计数排序 用时：0 ms
std::sort 用时：18 ms
 得出结论，选择快速排序是最好的选择
 * */


/***************************
 * 冒泡排序（基本版）
 ***************************/
/***********************************************************************************************************
*
* 算法描述：冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序
*           错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
*           这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
*
* 实现步骤：
*          1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
*          2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
*          3. 针对所有的元素重复以上的步骤，除了最后一个；
*          4. 重复步骤1~3，直到排序完成。
*
*
***********************************************************************************************************/
template <typename T>
void bubble_sort(T a[], size_t size) {
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size - i - 1; ++j) {
            if (a[j] > a[j + 1]) {
                T tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

/***************************
 * 冒泡排序（优化版）
 ***************************/
/***********************************************************************************************************
*
* 算法描述：冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序
*           错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
*           这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
*
* 实现步骤：
*          1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
*          2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
*          3. 记录最后一次交换元素的位置（pos），pos之后的位置没有发生交换，那就是已经有顺序的了；
*          4. 重复步骤1~3，直到排序完成。
* 时间复杂度：
*           最优情况：T(n) = O(n)，也就是说如果是已经有顺序的，那么就仅仅需要一趟比较就行
*           最差情况：T(n) = O(n^2)，
*           平均情况：T(n) = O(n^2)
*
***********************************************************************************************************/
template <typename T>
void bubble_sort_optimized(T a[], size_t size) {
    int i = size - 1;
    while (i > 0) {
        int pos = 0;
        for (int j = 0; j < i; ++j) {
            if (a[j] > a[j + 1]) {
                pos = j;
                T tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
        i = pos;
    }
}

/***************************
 * 选择排序
 ***************************/
/***********************************************************************************************************
*
* 算法描述：Selection-sort是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，
*           存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序
*           序列的末尾。以此类推，直到所有元素均排序完毕。
*
* 实现步骤：
*          1. 初始化是无序的状态，第一次排序默认a[0]最小，然后从a[1...n-1]中持续与最小值进行比较，找到
*             最小值后与a[0]交换；
*          2. 继续从a[2...n-1]寻找最小值与a[1]交换；
*          3. 重复排序，直到最后一个元素也有序
* 时间复杂度：
*           最优情况：T(n) = O(n^2)
*           最差情况：T(n) = O(n^2)
*           平均情况：T(n) = O(n^2)
*
***********************************************************************************************************/
template <typename T>
void select_sort(T a[], size_t size) {
    for (int i = 0; i < size; ++i) {
        int min_index = i;
        for (int j = i + 1; j < size; ++j) {
            if (a[j] < a[min_index]) {
                min_index = j;
            }
        }
        T tmp = a[i];
        a[i] = a[min_index];
        a[min_index] = tmp;
    }
}

/***************************
 * 插入排序（基本版）
 ***************************/
/***********************************************************************************************************
*
* 算法描述：插入排序对于未排序的的数据在已经排序的序列里插入到合适位置，这个合适位置就是从有序的序列里的最后
*           一个位置开始往前扫描，如果扫描到一个元素比该元素大（或小），那么该位置的后一个位置就是要插入的位置
*
* 实现步骤：
*
* 时间复杂度：
*           最优情况：T(n) = O(n^2)
*           最差情况：T(n) = O(n^2)
*           平均情况：T(n) = O(n^2)
*
***********************************************************************************************************/
template <typename T>
void insert_sort(T a[], size_t size) {
    for (int i = 1; i < size; ++i) {
        T value = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > value) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = value;
    }
}

/***************************
 * 插入排序（二分优化版）
 ***************************/
/***********************************************************************************************************
*
* 算法描述：对insert_sort的改进，就是在查找的使用可以采用折半查找
*           第一个突破O(n^2)的排序算法。
* 实现步骤：
*
* 时间复杂度：
*           最优情况：T(n) = O(n^2)
*           最差情况：T(n) = O(n^2)
*           平均情况：T(n) = O(n^2)
*
***********************************************************************************************************/
template <typename T>
void insert_sort_binary(T a[], size_t size) {
    for (int i = 1; i < size; ++i) {
        T value = a[i];
        int left = 0, right = i - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (value > a[mid])
                left = mid + 1;
            else
                right = mid - 1;
        }
        for (int j = i - 1; j >= left; --j) {
            a[j + 1] = a[j];
        }
        a[left] = value;
    }
}

/***************************
 * 希尔排序
 ***************************/
/***********************************************************************************************************
*
* 算法描述：1959年Shell发明；第一个突破O(n^2)的排序算法；是简单插入排序的改进版；它与插入排序的不同之处在于，
*           它会优先比较距离较远的元素。希尔排序又叫缩小增量排序，先将整个待排序的记录序列分割成为若干子序列
*           分别进行直接插入排序。
*
* 实现步骤：
*          1. 选择一个增量序列gap[1]，gap[2]，…，gap[k]，其中gap[i]>gap[j](i > j)，gap[k]=1；
*          2. 按增量序列个数k，对序列进行k 趟排序；
*          3. 每趟排序，根据对应的增量gap[i]，将待排序列分割成若干长度为size/gap[i] 的子序列，分别对各子表
*             进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
*
* 时间复杂度：
*           最优情况：T(n) = O(n*log2n)
*           最差情况：T(n) = O(n*log2n)
*           平均情况：T(n) = O(n*logn)
*
***********************************************************************************************************/
template <typename T>
void shell_sort(T a[], size_t size) {
    for (int gap = size / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < size; ++i) {
            T temp = a[i];
            int j = i;
            while (j >= gap && a[j - gap] > temp) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = temp;
        }
    }
}

/***************************
 * 归并排序（非递归）
 ***************************/
/***********************************************************************************************************
*
* 算法描述：非递归实现 -- 自底向上
*           将数组中的相邻元素两两配对。用merge函数将他们排序，
*           构成n/2组长度为2的排序好的子数组段，然后再将他们排序成长度为4的子数组段，
*           如此继续下去，直至整个数组排好序。。
* 实现步骤：
*
* 时间复杂度：
*           最优情况：T(n) = O(n)
*           最差情况：T(n) = O(n*logn)
*           平均情况：T(n) = O(n*logn)
*
***********************************************************************************************************/
template <typename T>
void merge_sort(T a[], size_t size) {
    T* tmp = new T[size];
    for (int width = 1; width < size; width *= 2) {
        for (int i = 0; i < size; i += 2 * width) {
            int left = i;
            int mid = std::min(i + width, (int)size);
            int right = std::min(i + 2 * width, (int)size);

            int idx = 0, l = left, r = mid;
            while (l < mid && r < right) {
                tmp[idx++] = (a[l] <= a[r]) ? a[l++] : a[r++];
            }
            while (l < mid) tmp[idx++] = a[l++];
            while (r < right) tmp[idx++] = a[r++];

            for (int j = 0; j < idx; ++j) {
                a[left + j] = tmp[j];
            }
        }
    }
    delete[] tmp;
}

/***************************
 * 快速排序
 ***************************/
/***********************************************************************************************************
*
* 算法描述：快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高! 它是
*           处理大数据最快的排序算法之一了。
*           通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别
*           对这两部分记录继续进行排序，以达到整个序列有序。
*
* 实现步骤：
*          1. 从数列中挑出一个元素，称为 "基准"（pivot）；
*          2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数
*		       可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
*          3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
*
* 时间复杂度：
*           最优情况：T(n) = O(n)
*           最差情况：T(n) = O(n*logn)
*           平均情况：T(n) = O(n*logn)
*
***********************************************************************************************************/
template <typename T>
void quick_sort(T a[], size_t size) {
    if (size < 2) return;
    T pivot = a[size / 2];
    int left = 0, right = size - 1;
    while (left <= right) {
        while (a[left] < pivot) ++left;
        while (a[right] > pivot) --right;
        if (left <= right) {
            T tmp = a[left];
            a[left++] = a[right];
            a[right--] = tmp;
        }
    }
    quick_sort(a, right + 1);
    quick_sort(a + left, size - left);
}

/***************************
 * 堆排序
 ***************************/
/***********************************************************************************************************
*
* 算法描述：是指利用堆这种数据结构所设计的一种排序算法。二叉堆是一个完全二叉树的结构，并同时满足堆的性质：
*           1. 即子结点的键值或索引总是小于（或者大于）它的父节点。
*           2. 父节点和子节点满足某种序列
*
* 实现步骤：
*         1. 将初始待排序关键字序列(R0,R1....Rn-1)构建成大顶堆，构建的过程就是每次把R[i]的元素向上调整，
*            此堆为初始的无序区；
*         2. 将堆顶元素R0与最后一个元素R[n-1]交换，此时得到新的无序区(R0,R2,......Rn-2)和新的有序区(Rn),
             且满足R[0,1...n-2]<=R[n-1]；
*         3. 在第二步后，堆可能无序了，需要对堆逐步向下调整，一直满足堆得特性才行。
*         4. 循环第二步和第三步，直到堆得最后一个元素调整完毕。
*
* 时间复杂度：
*           最优情况：T(n) = O(n*logn)
*           最差情况：T(n) = O(n^2)
*           平均情况：T(n) = O(n*logn)
*
***********************************************************************************************************/
template <typename T>
void heap_sort(T a[], size_t size) {
    // 建堆（上浮调整）
    for (int i = 1; i < size; ++i) {
        int cur = i;
        while (cur > 0) {
            int parent = (cur - 1) / 2;
            if (a[cur] > a[parent]) {
                std::swap(a[cur], a[parent]);
                cur = parent;
            } else {
                break;
            }
        }
    }

    // 逐个取出堆顶元素（下沉调整）
    for (int i = size - 1; i > 0; --i) {
        std::swap(a[0], a[i]);
        int cur = 0, child = 1;
        while (child < i) {
            if (child + 1 < i && a[child + 1] > a[child])
                ++child;
            if (a[child] > a[cur]) {
                std::swap(a[child], a[cur]);
                cur = child;
                child = 2 * cur + 1;
            } else break;
        }
    }
}

/***************************
 * 计数排序（非负整数，最大值≤RANDMAX）
 ***************************/
/***********************************************************************************************************
*
* 算法描述：计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序
*           数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
*           它是最快的排序算法，但是因为其对所排序的元素必须要是整数，所以限制了其的应用
*
* 实现步骤：
*         1. 找出待排序的数组中最大和最小的元素；(Lee哥在这里偷懒了，直接使用了RANDMAX，表示排序的元素是0~RANDMAX)
*         2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
*         3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；这个累加就是让C[i]计数了有多少个元素
*            少于或者等于i的元素，方便了反向输出元素时找到元素存放在数组a中的下标。
*         4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
*
* 时间复杂度：
*           线性时间
*           最优情况：T(n) = O(n + RANDMAX)
*           最差情况：T(n) = O(n + RANDMAX)
*           平均情况：T(n) = O(n + RANDMAX)
*
* 缺点：1. 元素不能是负数；
*       2. 额外申请了内存，如果元素值很大，怎么办？
*
***********************************************************************************************************/
#define RANDMAX 100
template <typename T>
void count_sort(T a[], size_t size) {
    T* counts = (T*)calloc(RANDMAX, sizeof(T));
    T* sorted = (T*)calloc(size, sizeof(T));

    for (int i = 0; i < size; ++i)
        ++counts[a[i]];

    for (int i = 1; i < RANDMAX; ++i)
        counts[i] += counts[i - 1];

    for (int i = size - 1; i >= 0; --i) {
        sorted[counts[a[i]] - 1] = a[i];
        --counts[a[i]];
    }

    memcpy(a, sorted, size * sizeof(T));
    free(counts);
    free(sorted);
}

#endif // __DONGNAOEDU_SORT_HPP__
